/**
 * 
 */
package leetCode;

import java.util.HashMap;

/**
 * 树的深度<5,可以用3维的数组表示 百位代表深度1~4 十位代表所在层次的编号P：1~8，和满二叉树一样对应 个位：节点值
 * 输入增序的3位整数，返回所有根节点到叶节点路径的和
 * 
 * @author zhongfang
 *
 */
public class pathsumiv {
	class Node {
		int val;
		Node parent;
	}

	public int pathSum(int[] nums) {
		int sum = 0;
		// 需要考虑的是每个节点被加几次，即每个节点的叶节点个数
		HashMap<Integer, Node> leaves = new HashMap<>(nums.length);
		HashMap<Integer, Node> allNodes = new HashMap<>(nums.length);
		for (int i : nums) {
			int level = i / 100;
			int levelCode = i / 10 % 10;
			int val = i % 10;

			int code = ((int) (Math.pow(2, level - 1)) - 1 + levelCode);// 自己的编号
			int parentCode = code >> 1;
			Node node = new Node();
			node.parent = allNodes.get(parentCode);
			node.val = val;
			leaves.put(code, node);
			leaves.remove(parentCode);
			allNodes.put(code, node);
		}

		for (Node node : leaves.values()) {
			while (node != null) {
				sum += node.val;
				node = node.parent;
			}
		}
		return sum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums = { 113, 221 };
		System.out.println(new pathsumiv().pathSum(nums));
	}

}
